The invention relates generally to network multi-path routing. More specifically, the invention relates to systems and methods that enables dynamic load balancing using multi-path Border Gateway Protocol (BGP) mechanisms. Standard (static) multi-path BGP mechanisms are combined with an Intelligent Route Service Control Point (IRSCP) architecture that uses dynamic load information and calculates an optimal load balancing proportion across multiple paths.
Today's Internet comprises multiple Autonomous Systems (ASs) and BGP is the de facto standard routing protocol to exchange routing information between ASs. A pair of neighboring ASs typically have multiple peering points where they exchange through BGP sessions BGP control messages that contain routing information. BGP peering sessions between different ASs are referred to as external BGP (eBGP) sessions. Within an AS, BGP is also used to exchange BGP learned routes between routers and are referred to as internal BGP (iBGP) sessions.
Multi-path routing is a routing technique that leverages multiple alternative paths through a network to yield a variety of benefits such as fault tolerance, increased bandwidth, or improved security. FIG. 1 shows five routers R1, R2, R3, R4 and R5 in AS X and five routers R6, R7, R8, R9 and R10 in AS Y. The two ASs use three routers as peering routers between the ASs, R2-R7, R3-R6 and R4-R10. The peering routers are configured with eBGP sessions between them for the exchange of routing information (solid lines). iBGP sessions are shown (broken lines) between the routers in AS X and AS Y and an AS specific iBGP route distribution entity. In traditional IP networks the route distribution entity is a Route Reflector (RR). An RR only distributes routes without applying any policies and/or modification. An alternative approach constitutes the use of a route distribution function that also applies policies and as a result may manipulate or change the routes it distributes. This approach is allowed by an Intelligent Route Service Control Point (IRSCP) architecture.
The IRSCP architecture allows a network operator to flexibly control routing between the traffic ingresses and egresses within an ISP's network without modifying the ISP's existing routers. The IRSCP subsumes the control plane of an ISP's network by replacing the distributed BGP decision process of each router in the network with a flexible, logically centralized application controlled route computation. The IRSCP supplements the traditional BGP decision process with an explicitly ranked decision process that allows route control applications to provide a per-destination, per-router explicit ranking of traffic egresses.
The IRSCP advertises an appropriate set of link bandwidth values (not necessarily the same as the actual static link bandwidth values) to routers. On receiving these routes from the IRSCP, the routers follow normal routing selection processes as dictated by protocol standards. However, because the link bandwidth values associated with these routes have been calculated as part of the IRSCP load balancing algorithm, the routers execute this load balancing decision by the IRSCP by just following the normal protocol processing without realizing what is happening behind the scene.
FIG. 1 shows if a host H or network is reachable through router R9. The prefix associated with the host H will be advertised to router R9 (typically using eBGP), and from router R9 the route will be distributed throughout AS Y. In turn, AS Y advertises the route to its BGP neighbors using BGP sessions of its peering routers. For example, router R2 will learn the route information from router R7, router R3 from router R6, and router R4 from router R10. Router R1 and all other routers in AS X will learn of the route to host H from all three peering routers R2, R3 and R4.
To select between these different options, ASs employ a policy known as hot potato routing whereby the route received from the nearest peering router is selected. If the distance or cost from router R1 to router R2, router R3 and router R4 is 1, 3 and 3 respectively, router R1's nearest exit is router R2, and a packet to host H uses the link between router R2 and router R7 to reach AS Y. After the packet reaches AS Y, all routing decisions are made by AS Y, and AS X has no control over how the packet is ultimately routed to reach host H.
Although BGP by default selects only one egress point for a given destination, routers may be configured so that multiple egress points may be used and perform load balancing. Using this multi-path BGP extension, all equal cost paths to a specific destination may be used to forward traffic to a destination. Further, traffic towards this destination may be load balanced according to the static link capacities of the peering links associated with the paths.
To configure BGP to distribute traffic proportionally over external links with unequal bandwidth when multi-path load balancing is enabled, the bgp dmzlink-bw command is used in the address family configuration mode. This command must be entered on each router that contains an external interface that is to be used for multi-path load balancing.
The bgp dmzlink-bw command is used to configure BGP to distribute traffic proportionally to the bandwidth of external links. This command is configured for multi-path load balancing between directly connected eBGP neighbors. This feature is used with BGP multi-path features to configure load balancing over links with unequal bandwidth. The neighbor dmzlink-bw command must also be configured for each external link through which multi-path load balancing is configured to advertise the link bandwidth as an extended community. The neighbor send-community command is configured to exchange the link bandwidth extended community with iBGP peers.
The neighbor dmzlink-bw command is used to configure BGP to advertise the bandwidth of the specified external interface as an extended community. This command is configured for links between directly connected eBGP neighbors. The link bandwidth extended community attribute is propagated to iBGP peers when extended community exchange is enabled with the neighbor send-community command. This feature is used with BGP multi-path features to configure load balancing over links with unequal bandwidth. This feature is not enabled until the bgp dmzlink-bw command is entered under the address family session for each router that has a directly connected external link.
For example, in FIG. 2 the distance from router R5 to routers R2, R3 and R4 is 2, 3, and 2, respectively. Because router R5 has the same cost or distance to routers R2 and R4, it may use both egress routers for traffic destined to host H using the multi-path BGP extension. However, it is possible that the peering links at routers R2 and R4 have different link capacity, for example, 1 Gbps and 2 Gbps. In this case, it would be desirable for router R4 to have two times as much traffic as router R2. To enable such differentiation, multi-path BGP defines an extended community value for the link bandwidth. Using this attribute, routers R2 and R4 respectively can inform R5 that their peering link capacity is 1 Gbps and 2 Gbps (i.e., these community values are included in the BGP routes for host H that routers R2 and R4 advertise in AS X). Then, when router R5 selects an egress router to reach host H, it can load balance by sending ⅓ of its traffic to router R2 and ⅔ of its traffic to router R4.
Although multi-path BGP provides a mechanism to enable multi-path routing and load balancing, the value used for the load balancing decision is static and does not deal with dynamic load change. This limitation can lead to undesirable consequences.